#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
#include<inttypes.h>
#include"big_int.h"
#include"func.h"

void big_unsigned_compress(big_unsigned *this){
    for(size_t i=this->size-1;~i;i--)
        if(this->num[i]){
            this->size=i+1;
            return;
        }
    this->size=0;
}

big_unsigned big_unsigned_rand(rand_dev *p_rand,size_t bytes){
    big_unsigned result;
    result.size=(bytes+3)>>2;
    result.num=calloc(result.size,sizeof(uint32_t));
    rand_dev_rand_array(p_rand,result.num,bytes);
    ((uint8_t*)result.num)[bytes-1]|=0x80;
    return result;
}
big_unsigned big_unsigned_from_unsigned(uint32_t num){
    big_unsigned result;
    if(num){
        result.size=1;
        result.num=malloc(sizeof(uint32_t));
        *result.num=num;
    }
    else{
        result.size=0;
        result.num=NULL;
    }
    return result;
}
big_unsigned big_unsigned_from_string(const char *str){
    big_unsigned result={NULL,0};
    while(ISDIGIT(*str)){
        big_unsigned_multiply_unsigned(&result,10);
        big_unsigned tmp=big_unsigned_from_unsigned(*str++ - '0');
        big_unsigned_add(&result,&tmp);
        big_unsigned_destruct(&tmp);
    }
    return result;
}
big_unsigned big_unsigned_copy(const big_unsigned *that){
    big_unsigned result;
    result.size=that->size;
    if(result.size){
        result.num=malloc(result.size*sizeof(uint32_t));
        for(size_t i=0;i<result.size;i++)
            result.num[i]=that->num[i];
    }
    else
        result.num=NULL;
    return result;
}
void big_unsigned_destruct(big_unsigned *this){
    free(this->num);
}
void big_unsigned_print(const big_unsigned *this){
    big_unsigned tmp=big_unsigned_copy(this);
    size_t buf_size=this->size*108/100+2;
    uint32_t *buf=malloc(buf_size*sizeof(uint32_t));
    size_t i;
    for(i=0;i<buf_size && big_unsigned_not_zero(&tmp);i++)
        buf[i]=big_unsigned_div_unsigned(&tmp,1000000000);
    assert(("buf is not large enough",i<buf_size));
    if(i==0)
        putchar('0');
    else{
        printf("%"PRIu32,buf[i-1]);
        for(size_t j=i-2;~j;j--)
            printf("%09"PRIu32,buf[j]);
    }
    free(buf);
    big_unsigned_destruct(&tmp);
}
void big_unsigned_decline(big_unsigned *this){
    assert(big_unsigned_not_zero(this));
    for(size_t i=0;i<this->size;i++)
        if(this->num[i]--)
            break;
    if(this->num[this->size-1]==0)
        this->size--;
}
void big_unsigned_add(big_unsigned* restrict this,const big_unsigned* restrict that){
    uint64_t carry=0;
    size_t new_size=MAX(this->size,that->size);
    this->num=realloc(this->num,(new_size+1)*sizeof(uint32_t));
    for(size_t i=this->size;i<new_size;i++)
        this->num[i]=0;
    this->size=new_size;
    for(size_t i=0;i<that->size;i++){
        carry+=this->num[i];
        carry+=that->num[i];
        this->num[i]=carry;
        carry>>=32;
    }
    if(carry){
        size_t i;
        for(i=that->size;i<new_size;i++)
            if(++this->num[i])
                break;
        if(i==new_size)
            this->num[this->size++]=1;
    }
}
void big_unsigned_subtract(big_unsigned* restrict this,const big_unsigned* restrict that){
    uint64_t carry=0;
    assert(("this<that",this->size >= that->size));
    for(size_t i=0;i<that->size;i++){
        uint64_t tmp=0x100000000+this->num[i]-that->num[i]-carry;
        this->num[i]=tmp;
        carry=1-(tmp>>32);
    }
    if(carry){
        assert(("this<that",this->size!=that->size));
        size_t i;
        for(i=that->size;i<this->size;i++)
            if(this->num[i]--)
                break;
    }
    big_unsigned_compress(this);
}
void big_unsigned_multiply_unsigned(big_unsigned *this,uint32_t that){
    if(that==0){
        this->size=0;
        return;
    }
    uint64_t carry=0;
    for(size_t i=0;i<this->size;i++){
        uint64_t tmp=this->num[i];
        tmp*=that;
        tmp+=carry;
        this->num[i]=tmp;
        carry=tmp>>32;
    }
    if(carry){
        this->num=realloc(this->num,(this->size+1)*sizeof(uint32_t));
        this->num[this->size++]=carry;
    }
}
void big_unsigned_mod_multiply(big_unsigned *this,const big_unsigned *that,const big_unsigned* restrict mod){
    const big_unsigned *x;
    const big_unsigned *y;
    if(this->size<that->size){
        x=that;
        y=this;
    }
    else{
        x=this;
        y=that;
    }
    big_unsigned result={NULL,0};
    for(size_t i=y->size-1;~i;i--){
        for(int j=0;j<32;j++){
            big_unsigned_lshift(&result,1);
            if(big_unsigned_cmp(&result,mod)>=0)
                big_unsigned_subtract(&result,mod);
            if(y->num[i]&(1<<(31-j))){
                big_unsigned_add(&result,x);
                if(big_unsigned_cmp(&result,mod)>=0)
                    big_unsigned_subtract(&result,mod);
            }
        }
    }
    big_unsigned_destruct(this);
    *this=result;
}
uint32_t big_unsigned_div_unsigned(big_unsigned *this,uint32_t that){
    assert(that!=0);
    uint64_t rem=0;
    for(size_t i=this->size-1;~i;i--){
        rem<<=32;
        rem|=this->num[i];
        this->num[i]=rem/that;
        rem%=that;
    }
    if(this->size && this->num[this->size-1]==0)
        this->size--;
    return rem;
}
int big_unsigned_cmp(const big_unsigned *p_x,const big_unsigned *p_y){
    if(p_y->size > p_x->size)
        return -1;
    if(p_y->size < p_x->size)
        return 1;
    for(size_t i=p_y->size-1;~i;i--){
        if(p_x->num[i] < p_y->num[i])
            return -1;
        if(p_x->num[i] > p_y->num[i])
            return 1;
    }
    return 0;
}
int big_unsigned_not_zero(const big_unsigned *this){
    return this->size;
}
int big_unsigned_is_odd(const big_unsigned *this){
    return this->size && this->num[0]&1;
}
size_t big_unsigned_lowbit(const big_unsigned *this){
    uint32_t tmp;
    for(size_t i=0;i<this->size;i++)
        if((tmp=LOWBIT(this->num[i]))){
            size_t result=i<<5; // i*32
            while(!(tmp&1)){
                result++;
                tmp>>=1;
            }
            return result;
        }
    return ~(size_t)0;
}
void big_unsigned_rshift(big_unsigned *this,size_t bits){
    size_t size=bits>>5;        // bits/32
    size_t remain_bits=bits&31; // bits%32
    size_t mask=(1<<remain_bits)-1;
    uint32_t remain=0;
    if(size){
        for(size_t i=0;i+size<this->size;i++)
            this->num[i]=this->num[i+size];
        if(this->size<=size)
            this->size=0;
        else
            this->size-=size;
    }
    if(remain_bits){
        for(size_t i=this->size-1;~i;i--){
            uint32_t tmp_remain=this->num[i]&mask;
            this->num[i]>>=remain_bits;
            this->num[i]|=remain<<(32-remain_bits);
            remain=tmp_remain;
        }
        if(this->size && this->num[this->size-1]==0)
            this->size--;
    }
}
void big_unsigned_lshift(big_unsigned *this,size_t bits){
    size_t size=bits>>5;        // bits/32
    size_t remain_bits=bits&31; // bits%32
    if(!big_unsigned_not_zero(this))
        return;
    if(size){
        this->num=realloc(this->num,(this->size+size)*sizeof(uint32_t));
        for(size_t i=this->size-1;~i;i--)
            this->num[i+size]=this->num[i];
        for(size_t i=0;i<size;i++)
            this->num[i]=0;
        this->size+=size;
    }
    if(remain_bits){
        size_t mask=(1<<remain_bits)-1;
        uint32_t remain=0;
        for(size_t i=0;i<this->size;i++){
            uint32_t tmp_remain=(this->num[i]>>(32-remain_bits))&mask;
            this->num[i]<<=remain_bits;
            this->num[i]|=remain;
            remain=tmp_remain;
        }
        if(remain){
            this->num=realloc(this->num,(this->size+1)*sizeof(uint32_t));
            this->num[this->size++]=remain;
        }
    }
}
big_unsigned big_unsigned_mod_power(uint32_t base,const big_unsigned* restrict index,const big_unsigned* restrict mod){
    big_unsigned result=big_unsigned_from_unsigned(1);
    big_unsigned big_base=big_unsigned_from_unsigned(base);
    for(size_t i=index->size-1;~i;i--){
        uint32_t tmp=index->num[i];
        for(int j=0;j<32;j++){
            big_unsigned_mod_multiply(&result,&result,mod);
            if(tmp&0x80000000)
                big_unsigned_mod_multiply(&result,&big_base,mod);
            tmp<<=1;
        }
    }
    big_unsigned_destruct(&big_base);
    return result;
}